package cc.wsyw126.java.nowcoder.sword_offer;

/**
 * Created by Administrator on 2017/4/13.
 */
public class CloneList {
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) return pHead;
        //copy
        doCopy(pHead);
        //rebuild random
        doRandom(pHead);
        //clone
        RandomListNode newRoot = doClone(pHead);
        return newRoot;
    }

    private RandomListNode doClone(RandomListNode pHead) {
        RandomListNode root = pHead.next;
        while (pHead != null && pHead.next.next != null) {
            RandomListNode next = pHead.next;
            pHead = next.next;
            next.next = next.next.next;
        }
        return root;
    }

    private void doRandom(RandomListNode pHead) {
        RandomListNode temp = pHead;
        while (temp != null) {
            RandomListNode random = temp.random;
            if (random != null) {
                temp.next.random = random.next;
            }
            temp = temp.next.next;
        }
    }

    private void doCopy(RandomListNode pHead) {
        RandomListNode temp = pHead;
        while (temp != null) {
            RandomListNode randomListNode = new RandomListNode(temp.label);
            RandomListNode next = temp.next;
            temp.next = randomListNode;
            randomListNode.next = next;
            temp = next;
        }
    }

    private class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public static void main(String[] args) {
        CloneList cloneList = new CloneList();
        RandomListNode root1 = cloneList.new RandomListNode(1);
        RandomListNode root2 = cloneList.new RandomListNode(2);
        RandomListNode root3 = cloneList.new RandomListNode(3);
        RandomListNode root4 = cloneList.new RandomListNode(4);
        RandomListNode root5 = cloneList.new RandomListNode(5);
        root1.next = root2;
        root2.next = root3;
        root3.next = root4;
        root4.next = root5;
        root1.random = root3;
        root4.random = root2;
        root2.random = root5;
        RandomListNode newroot = cloneList.Clone(root1);
        root1.label=10;root2.label=20;root3.label=30;root4.label=40;root5.label=50;
        RandomListNode clone = newroot;
        while (clone != null) {
            System.out.print(clone.label);
            clone = clone.next;
        }

        System.out.println();
        clone = newroot;
        while (clone != null) {
            System.out.print(clone.random == null ? "#" : clone.random.label);
            clone = clone.next;
        }
    }
}
